package Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

/**
 * dp数组定义为从第几家开始打劫
 */
public class 打家劫舍 {
    static int[] memo;
    public static int rob(int[] nums) {
        memo=new int[nums.length];
        Arrays.fill(memo,-1);
        return dp(nums,0);
    }

    static int dp(int[] nums,int start){
        if (start >= nums.length) {
            return 0;
        }
        if(memo[start]!=-1){
            return memo[start];
        }
        memo[start]=Math.max(dp(nums,start+1),nums[start]+dp(nums,start+2));
        return memo[start];
    }
    /************************************               TWO               ********************************************************/
    //房屋是连着的
    static int[] memo1;
    static int[] memo2;
    public static int rob2(int[] nums) {
        int n=nums.length;
        memo1=new int[nums.length];
        memo2=new int[nums.length];
        Arrays.fill(memo1,-1);
        Arrays.fill(memo2,-1);
        //不同点
        return Math.max(dp2(nums,0,n-2,memo1),dp2(nums,1,n-1,memo2));
    }

    static int dp2(int[] nums,int start,int end,int[] memo){
        //不同点
        if (start >= end) {
            return 0;
        }
        if(memo[start]!=-1){
            return memo[start];
        }
        //不同点
        memo[start]=Math.max(dp2(nums,start+1,end,memo),nums[start]+dp2(nums,start+2,end,memo));
        return memo[start];
    }
    /************************************               THREE               ********************************************************/

    //二叉树版本
    HashMap<TreeNode,Integer> memory=new HashMap<>();
    public int rob(TreeNode root) {
        if(root==null) return 0;
        if(memory.containsKey(root)) return memory.get(root);
        int doit=root.val+(root.left==null?0:rob(root.left.left)+rob(root.left.right))+(root.right==null?0:rob(root.right.right)+rob(root.right.left));
        int dont=rob(root.left)+rob(root.right);
        memory.put(root,Math.max(doit,dont));
        return Math.max(doit,dont);
    }
    /**********************************************************测试***************************************************************/
    public static void main(String[] args) {
        int[] arr={2,3,2};
        System.out.println(rob2(arr));
    }
}
